import functools


# class Solution(object):
#     def generateAbbreviations(self, word):
#         """
#         :type word: str
#         :rtype: List[str]
#         """
#         n = len(word)
# 
#         @functools.cache
#         def search(i):
#             out = []
#             if i == 0:
#                 j = i
#                 while j < n - 1:
#                     out2 = search(j + 1)
#                     for item in out2:
#                         out.append(str(j - i + 1) + item)
#                     j += 1
#                 out.append(str(j - i + 1))
#             if i < n - 1:
#                 j = i
#                 while j < n - 1:
#                     out2 = search(j + 1)
#                     for item in out2:
#                         if j - i > 0:
#                             out.append(word[i] + str(j - i) + item)
#                         else:
#                             out.append(word[i] + item)
#                     j += 1
#                 if i < n - 1:
#                     out.append(word[i] + str(n - 1 - i))
#             else:
#                 if i == 0:
#                     return [word[n - 1], '1']
#                 else:
#                     return [word[n - 1]]
#             return out
#         return search(0)

class Solution(object):
    def generateAbbreviations(self, word):
        """
        :type word: str
        :rtype: List[str]
        """
        n = len(word)
        s_list = []


        def suoxie(k):
            state = 0
            s = ''
            num = 0
            i = 0
            k_index = 0
            while k_index < n:
                if state == 0:
                    if k & 1 == 0:
                        s += word[i]
                        i += 1
                    else:
                        num += 1
                        state = 1
                else:
                    if k & 1 == 0:
                        s += str(num)
                        i += num
                        s += word[i]
                        state = 0
                        num = 0
                        i += 1
                    else:
                        num += 1
                k_index += 1
                k = k >> 1
            if state:
                s += str(num)
            return s

        for i in range(2 ** n):
            s = suoxie(i)
            s_list.append(s)
        return s_list

data = Solution()
word = 'mav'
print(data.generateAbbreviations(word))
word = 'a'
print(data.generateAbbreviations(word))